public class Solution21 {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode head = new ListNode(), tail = head;
        ListNode tmpNode1 = list1, tmpNode2 = list2;
        while(tmpNode1 != null && tmpNode2 != null){
            if(tmpNode1.val < tmpNode2.val){
                tail.next = tmpNode1;
                tmpNode1 = tmpNode1.next;
            }
            else {
                tail.next = tmpNode2;
                tmpNode2 = tmpNode2.next;
            }
            tail = tail.next;
        }
        while(tmpNode1 != null){
            tail.next = tmpNode1;
            tmpNode1 = tmpNode1.next;
            tail = tail.next;
        }
        while(tmpNode2 != null){
            tail.next = tmpNode2;
            tmpNode2 = tmpNode2.next;
            tail = tail.next;
        }
        return head.next;
    }
}
